package solution17;

import java.util.LinkedList;
import java.util.List;

/**
 *  For each digit added, remove and copy every element in the queue and add the possible letter to each element,
 *  then add the updated elements back into queue again. Repeat this procedure until all the digits are iterated.
 *
 *  例如：234
 *  先匹配2，将2对应的a,b,c依次加入队列头
 *  然后匹配3，从队列中依次删除并复制之前加入的a,b,c，然后分别和3对应的d,e,f分别加一起加入队列尾
 *  如删除a，加入ad，ae,af, 删除b,加入bd,be,bf，删除c,加入cd,ce,cf，最好队列存储的字符串为：
 *  ad,ae,af,    bd,be,bf,  cd,ce,cf
 *  再匹配4，规律如下，删除ad,加入adg,adh,adi,删除ae,加入aeg,aeh,aei,循环下去，
 *  循环的条件是list.peek().length()==i(i从0开始)
 *
 */
public class Solution {
    public List<String> letterCombinations(String digits) {
        // 使用双向链表作为队列
        LinkedList<String> list = new LinkedList<>();
        if (digits == null || digits.length() == 0) {
            return list;
        }
        // 映射关系表
        String[] mapping = new String[] {"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        list.add("");
        for (int i = 0, n = digits.length();i < n; i++) {
            int x = Character.getNumericValue(digits.charAt(i));
            // digits的长度决定了返回的每个字符串的长度
            // remove and copy every element in the queue,and add the possible letter to each element
            while (list.peek().length()==i){
                // 取回digits的前i-1个数字所mapping的字符串，从队列头删除
                String t= list.remove();
                // 将digits的第i个数字mapping的每一个字母和前面digits的前i-1个数字组成的字符串再组合在一起加入队列尾
                for (char s : mapping[x].toCharArray()) {
                    list.add(t + s);
                }
            }
        }
        return list;
    }
}
